{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Facility Location"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective and Prerequisites\n",
    "\n",
    "Facility location problems can be commonly found in many industries, including logistics and telecommunications. In this example, we’ll show you how to tackle a facility location problem that involves determining the number and location of warehouses that are needed to supply a group of supermarkets. We’ll demonstrate how to construct a mixed-integer programming (MIP) model of this problem, implement this model in the Gurobi Python API, and then use the Gurobi Optimizer to find an optimal solution.\n",
    "\n",
    "This modeling example is at the beginner level, where we assume that you know Python and that you have some knowledge about building mathematical optimization models.\n",
    "\n",
    "**Download the Repository** <br />\n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "\n",
    "The study of facility location problems - also known as \"location analysis\" [1] - is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like safety (e.g. by avoiding placing hazardous materials near housing) and the location of  competitors' facilities.\n",
    "\n",
    "The Fermat-Weber problem, formulated in the 17'th century, was one of the first facility location problems ever devised. \n",
    "The Fermat-Weber problem can be described as follows: Given three points in a plane, find a fourth point such that the sum of its distances to the three given points is minimal. This problem can be viewed as a variation of the facility location problem, where the assumption is made that the transportation costs per distance are the same for all destinations.\n",
    "\n",
    "Facility location problems have applications in a wide variety of industries. For supply chain management and logistics, this problem  can be used to find the optimal location for stores, factories, warehouses, etc. Other applications range from public policy (e.g. positioning  police officers in a city), telecommunications (e.g. cell towers in a network), and even particle physics (e.g. separation distance between repulsive charges). Another application of the facility location problem is to determine the locations for natural gas transmission equipment. Finally, facility location problems can be applied to cluster analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "\n",
    "A large supermarket chain in the UK needs to build warehouses for a set of supermarkets it is opening in Northern England. The locations of the supermarkets have been identified, but the locations of the warehouses have yet to be determined.\n",
    "\n",
    "Several good candidate locations for the warehouses have been identified, but decisions must be made regarding \n",
    "how many warehouses to open and at which candidate locations to build them.\n",
    "\n",
    "Opening many warehouses would be advantageous as this would reduce the average distance a truck has to drive from the warehouse to the supermarket, and hence reduce the delivery cost. However, opening a warehouse has a fixed cost associated with it.\n",
    "\n",
    "In this example, our goal is to find the optimal tradeoff between delivery costs and the costs of building new facilities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex business problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components, namely:\n",
    "\n",
    "* Sets and indices.\n",
    "* Parameters.\n",
    "* Decision variables.\n",
    "* Objective function(s).\n",
    "* Constraints.\n",
    "\n",
    "We now present a MIP formulation for the facility location problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n",
    "\n",
    "### Sets and Indices\n",
    "\n",
    "$i \\in I$: Index and set of supermarket (or customer) locations.\n",
    "\n",
    "$j \\in J$: Index and set of candidate warehouse (or facility) locations.\n",
    "\n",
    "### Parameters\n",
    "\n",
    "$f_{j} \\in \\mathbb{R}^+$: Fixed cost associated with constructing facility $j \\in J$.\n",
    "\n",
    "$d_{i,j} \\in \\mathbb{R}^+$: Distance between facility $j \\in J$ and customer $i \\in I$.\n",
    "\n",
    "$c_{i,j} \\in \\mathbb{R}^+$: Cost of shipping between candidate facility site $j \\in J$ and customer location $i \\in I$. We assume that this cost is proportional to the distance between the facility and the customer. That is, $c_{i,j} = \\alpha \\cdot d_{i,j}$, where $\\alpha$ is the cost per mile of driving, adjusted to incorporate the average number of trips a delivery truck would be expected to make over a five year period.\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$select_{j} \\in \\{0, 1 \\}$: This variable is equal to 1 if we build a facility at candidate location $j \\in J$; and 0 otherwise.\n",
    "\n",
    "$0 \\leq assign_{i,j} \\leq 1$: This non-negative continuous variable determines the fraction of supply received by customer $i \\in I$ from facility $j \\in J$.\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "- **Total costs**. We want to minimize the total cost to open and operate the facilities. This is the sum of the cost of opening facilities and the cost related to shipping between facilities and customers. This total cost measures the tradeoff between the cost of building a new facility and the total delivery cost over a five year period.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Min} \\quad Z = \\sum_{j \\in J} f_{j} \\cdot select_{j} + \\sum_{j \\in J} \\sum_{i \\in I} c_{i,j} \\cdot assign_{i,j}\n",
    "\\tag{0}\n",
    "\\end{equation}\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Demand**. For each customer  $i \\in I$ ensure that its demand is fulfilled. That is, the sum of the fraction received from each facility for each customer must be equal to 1:\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J} assign_{i,j} = 1 \\quad \\forall i \\in I\n",
    "\\tag{1}\n",
    "\\end{equation}\n",
    "\n",
    "- **Shipping**. We need to ensure that we  only ship from facility $j \\in J$,  if that facility has actually been built.\n",
    "\n",
    "\\begin{equation}\n",
    "assign_{i,j} \\leq select_{j} \\quad \\forall i \\in I \\quad \\forall j \\in J\n",
    "\\tag{2}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "This example considers two supermarkets and nine warehouse candidates. The coordinates of each supermarket are provided in the following table.\n",
    "\n",
    "| <i></i> | Coordinates |  \n",
    "| --- | --- | \n",
    "| Supermarket 1 | (0,1.5) |\n",
    "| Supermarket 2 | (2.5,1.2) |\n",
    "\n",
    "The following table shows the coordinates of the candidate warehouse sites and the fixed cost of building the warehouse in millions of GBP.\n",
    "\n",
    "| <i></i> | coordinates | fixed cost |\n",
    "| --- | --- |  --- |\n",
    "| Warehouse 1 | (0,0) | 3 |\n",
    "| Warehouse 2 | (0,1) | 2 |\n",
    "| Warehouse 3 | (0,2) | 3 |\n",
    "| Warehouse 4 | (1,0) | 1 |\n",
    "| Warehouse 5 | (1,1) | 3 | \n",
    "| Warehouse 6 | (1,2) | 3 |\n",
    "| Warehouse 7 | (2,0) | 4 |\n",
    "| Warehouse 8 | (2,1) | 3 |  \n",
    "| Warehouse 9 | (2,2) | 2 |\n",
    "\n",
    "\n",
    "The cost per mile is one million GBP.\n",
    "\n",
    "## Python Implementation\n",
    "\n",
    "We now import the Gurobi Python Module and other Python libraries. Then, we initialize the data structures with the given data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "from math import sqrt\n",
    "\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Gurobi v9.1.0 and Python 3.7.0\n",
    "\n",
    "# Parameters\n",
    "customers = [(0,1.5), (2.5,1.2)]\n",
    "facilities = [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]\n",
    "setup_cost = [3,2,3,1,3,3,4,3,2]\n",
    "cost_per_mile = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Preprocessing\n",
    "\n",
    "We define a function that determines the Euclidean distance between each facility and customer sites. In addition, we compute key parameters required by the MIP model formulation of the facility location problem.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function determines the Euclidean distance between a facility and customer sites.\n",
    "\n",
    "def compute_distance(loc1, loc2):\n",
    "    dx = loc1[0] - loc2[0]\n",
    "    dy = loc1[1] - loc2[1]\n",
    "    return sqrt(dx*dx + dy*dy)\n",
    "\n",
    "# Compute key parameters of MIP model formulation\n",
    "\n",
    "num_facilities = len(facilities)\n",
    "num_customers = len(customers)\n",
    "cartesian_prod = list(product(range(num_customers), range(num_facilities)))\n",
    "\n",
    "# Compute shipping costs\n",
    "\n",
    "shipping_cost = {(c,f): cost_per_mile*compute_distance(customers[c], facilities[f]) for c, f in cartesian_prod}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model Deployment\n",
    "\n",
    "We now determine the MIP model for the facility location problem, by defining the decision variables, constraints, and objective function. Next, we start the optimization process and Gurobi finds the plan to build facilities that minimizes total costs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n",
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 20 rows, 27 columns and 54 nonzeros\n",
      "Model fingerprint: 0x0939f503\n",
      "Variable types: 18 continuous, 9 integer (9 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [5e-01, 4e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Presolve time: 0.00s\n",
      "Presolved: 20 rows, 27 columns, 54 nonzeros\n",
      "Variable types: 18 continuous, 9 integer (9 binary)\n",
      "\n",
      "Root relaxation: objective 4.723713e+00, 15 iterations, 0.00 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "*    0     0               0       4.7237129    4.72371  0.00%     -    0s\n",
      "\n",
      "Explored 0 nodes (15 simplex iterations) in 0.02 seconds\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 4.72371 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 4.723712908962e+00, best bound 4.723712908962e+00, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# MIP  model formulation\n",
    "\n",
    "m = gp.Model('facility_location')\n",
    "\n",
    "select = m.addVars(num_facilities, vtype=GRB.BINARY, name='Select')\n",
    "assign = m.addVars(cartesian_prod, ub=1, vtype=GRB.CONTINUOUS, name='Assign')\n",
    "\n",
    "m.addConstrs((assign[(c,f)] <= select[f] for c,f in cartesian_prod), name='Setup2ship')\n",
    "m.addConstrs((gp.quicksum(assign[(c,f)] for f in range(num_facilities)) == 1 for c in range(num_customers)), name='Demand')\n",
    "\n",
    "m.setObjective(select.prod(setup_cost)+assign.prod(shipping_cost), GRB.MINIMIZE)\n",
    "\n",
    "m.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "\n",
    "\n",
    "The result of the optimization model shows that the minimum total cost value is 4.72 million GBP. Let's see the solution that achieves that optimal result.\n",
    "\n",
    "### Warehouse Build Plan\n",
    "\n",
    "This plan determines at which site locations to build a warehouse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Build a warehouse at location 4.\n"
     ]
    }
   ],
   "source": [
    "# display optimal values of decision variables\n",
    "\n",
    "for facility in select.keys():\n",
    "    if (abs(select[facility].x) > 1e-6):\n",
    "        print(f\"\\n Build a warehouse at location {facility + 1}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shipment Plan \n",
    "\n",
    "This plan determines the percentage of shipments to be sent from each facility built to each customer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Supermarket 1 receives 100.0 % of its demand  from Warehouse 4 .\n",
      "\n",
      " Supermarket 2 receives 100.0 % of its demand  from Warehouse 4 .\n"
     ]
    }
   ],
   "source": [
    "# Shipments from facilities to customers.\n",
    "\n",
    "for customer, facility in assign.keys():\n",
    "    if (abs(assign[customer, facility].x) > 1e-6):\n",
    "        print(f\"\\n Supermarket {customer + 1} receives {round(100*assign[customer, facility].x, 2)} % of its demand  from Warehouse {facility + 1} .\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Conclusion\n",
    "In this example, we addressed a facility location problem where we want to build warehouses to supply a large number of supermarkets while minimizing the fixed total costs of building warehouses and the total variable shipping costs from warehouses to supermarkets. We learned how to formulate the problem as a MIP model. Also, we learned how to implement the MIP model formulation and solve it using the Gurobi Python API."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  References\n",
    "[1] Laporte, Gilbert, Stefan Nickel, and Saldanha da Gama, Francisco. Location Science. Springer, 2015."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
